A large class of modern embedded system computations can be expressed as a sequence of transformations on a stream of data. The sequence of transformations may be performed by an acyclic network of process stages hereby known as a “general pipeline” (or simply “pipeline”) with at least one start stage that accepts input data from external sources, at least one end stage which outputs data to external destinations, and some number of intermediate stages that accept data from at least one preceding stage, performs a specific computation or transformation and forwards its results to at least one subsequent stage. A simple example of a “general pipeline” is the common notion of a linear pipeline consisting of a linear sequence of processing stages, where the first stage of the pipeline accepts input data, and each subsequent stage of the pipeline may accept data from the previous stage, may perform a specific computation or transformation on the data, and may pass the result along to the next stage of the pipeline or, in the case of the last stage of a pipeline, output the data. This entire sequence of computations on a given set of input data is called a “task”, and the computation within each stage of the pipeline for that input data is called a “subtask”. In addition to the data that is passed between stages of the pipeline, control information may also be necessary to ensure the various stages of the pipeline perform their function at the appropriate time. Pipeline stages may be separated by buffers, e.g., registers, that may be used to store data between the various stages of the pipeline.
Each stage in the pipeline may, in general, compute for several cycles before passing the result to a subsequent stage. A clock signal may be used to control the flow of data through the various stages of the pipeline. Communication between adjacent stages of the pipeline may also be used to control the flow of data through the respective pipeline stages. This communication between stages is typically called handshaking. In this form of pipeline control, as output data from a preceding stage is available to the input of the subsequent stage, a control message may be sent between the stages to coordinate the activity between the stages. In other words, as data from a previous “producer” stage becomes available, it is written into a register or buffer, and an independent control signal may be sent to the subsequent “consumer” stage to indicate that the data is available for use. Once the consumer stage finishes reading the data from the register or input buffer, the consumer stage may also signal the producer stage that it has read the data from the register or buffer. Once the producer stage has received the communications from all the consumer stages, the producer stage may write new data to the register or the buffer for use in subsequent cycles without inadvertently overwriting data yet to be read.
One method of reducing the time required to process information in a pipeline is to overlap data processing between producer and consumer stages. One method of overlapping data processing may rely on doubling the number of registers or the size of the buffers available to store data between the various stages. By doubling the number of registers or the size of the buffers between the various stages, the producer stage may write into a first buffer or register prior to reading while the consumer stage simultaneously reads data from the previous task from the second buffer. In this manner, the producer stage is not delayed if the consumer stage is not ready so that the overall time for information to pass through the pipeline is reduced.
In addition to the input data, stages of a pipeline may require access to other information to perform the computation. For example, pipeline stages may require initialization or configuration to a predetermined state, or access to data stored in an external memory location before or during the computations or transformations in the stage.